package String.easy;

/**
 * 1. 问题描述
 *      给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
 *      具体的例子：
 *          1. abab由字串ab生成
 *          2. abcabcabcabc由abc生成
 *          3. abc不由任何字串生成
 *
 *      考虑一个具体的字符串 s = abc abc abc(长度为9的字符串)， 0,3,6起始
 *
 * 2. 算法思路
 *      首先我们第一想法就是能否找到目标字串，答案是可以的，此时我们就不能按正常的方式去从头遍历，我们可以从尾部遍历
 *      因为如果是由字串生成我们从后往前遍历，直到遍历到的字符与第一个字符相同，此时还没有完因为可能不是生成的字符串
 *      具体例子(abaaabaa此时生成字串为abaa,不是a，所以我们第一次找到与头字符相同的并不是我们需要的字串)，所以每
 *      次当我们找到一个与头相同的字符，此时就需要判断一下当前找到的字串是否可以生成目标串
 *      我额外又多写了一个子方法isgenerateString(String s,String sub),用于判断sub是否可以生成s，该方法的
 *      时间复杂度为O((s.length/sub.length) * sub.length)解释：s.length/sub.length是s中长度为sub.length
 *      的字串个数，每个字串需要O(sub.length)的遍历时间，所以最终为O((s.length/sub.length) * sub.length)
 *
 *      时间复杂度：O((s.length/sub.length) * sub.length) * n 约等于 O(n*2)
 *
 *      空间复杂度：该算法中需要消耗空间的只有从目标串中获取字串
 *
 * 3. 代码实现
 *
 */


public class 检测字符串是否有重复字串 {
    public static void main(String[] args) {
        String s = "abcabc";
        String sub = "abc";
        System.out.println(s.contains(sub));
    }


    /**
     *
     * 错误代码
     * @param s
     * @return
     */
    /*public static boolean repeatedSubstringPattern(String s) {
        // 前后指针法
        int i = 0; // 指向s的头部
        int j = s.length() - 1; // 指向s的尾部
        // 倒序遍历字符串s，让j向前移动，直到指向的字符与头部的字符相同就停止遍历
        for (int length = s.length() - 1; length > 0; length--) {
            if (s.charAt(length) != s.charAt(i)) {
                continue;
            }
            j = length;
            break;
        }
        // 此时j指向的字符与头部字符相同，j指向的字符就是可能为生成字串的起始字符，即我们找到了一个待定的生成字串
        // 下面的工作就是判断该字串是否为我们需要找到的字串,下面给出的算法有大量的回溯，所以时间复杂度比较高
        int sublen = s.length() - j; // 计算字串长度
        String target = s.substring(j,s.length()); // 目标字串
        System.out.println(target);
        if (s.length() % sublen != 0) {
            return false; // 如果时生成字串，其总长度可以被sulen整除
        }
        // 0,1,2 -- 0,3,6
        for (int l = 0; l < s.length() / sublen; l++) { // 出现的字串个数
            if (!s.substring(l*sublen,l*sublen+sublen).matches(target)) {
                return false;
            }
        }
        return true;
    }*/

    public static boolean repeatedSubstringPattern(String s) {
        int length = s.length();
        if (length == 1) {
            return false;
        }
        int j = length - 1;
        for (j = length - 1; j > 0; j--) {
            if (s.charAt(0) == s.charAt(j)) {
                // 此时找到了可能的字串
                String substr = s.substring(j,s.length()); // 获取当前字串
                int sublen = s.length() - j; // 获取当前字串长度
                // 判断此时的字串是否为生成字串
                boolean b = isgenerateString(s, substr);
                if (b == true) {
                    return b;
                }
            }
        }
        return false;
    }

    // 判断sub是否为s的字串
    public static boolean isgenerateString(String s,String sub) {
        if (s.length() % sub.length() != 0) {
            return false;
        }
        int length = s.length();
        int sublen = sub.length();
        for (int i = 0; i < length / sublen; i++) {
            if (!s.substring(i*sublen,i*sublen+sublen).matches(sub)){
                return false;
            }
        }
        return true;
    }
}
